package com.fufu.algorithem.sort;

import java.util.Arrays;

/**
 * @author: BlcakTiger
 * @date: 2023/2/24 10:48
 * @contact: hsf6661@163.com
 */
public class insert {

    public static void main(String[] args) {
//        int arr[] = {1,2,3,4,5};
//        sort(arr);
//        System.out.println(Arrays.toString(arr));
        //初始化数组
        int[] arr = new int[80000];
        //随机赋值
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random()*1000000);
        }
        //记录执行排序前的时间
        long ori = System.currentTimeMillis();
        //排序
        sort(arr);
        //记录排序后的时间
        long cur = System.currentTimeMillis();
        //计算时间
        System.out.println((cur-ori)*1.0/1000);
    }

    public static void sort(int[] arr){
        //待插入位置的索引
        int willInsertIndex;
        for (int i = 1; i < arr.length; i++) {
            //默认从有序数组的右边开始尝试插入
            willInsertIndex = i-1;
            //记录插入数
            int value = arr[i];
            //从插入数的左边第一位开始比较，若符合条件，让前面的元素往后移动，直到循环结束
            while (willInsertIndex>=0 && value>arr[willInsertIndex]){
                arr[willInsertIndex+1] = arr[willInsertIndex];
                //索引前移
                willInsertIndex--;
            }
            //如果willInsertIndex + 1 = i,则说明willInsertIndex一次都没有变化过，也就不需要交换了
            if (willInsertIndex+1<i){
                //这里索引+1是因为循环多执行了一次-1
                arr[willInsertIndex+1] = value;
            }
        }
    }
}
